#include "temu.h"
#include "stdlib.h"
#include <elf.h>

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <sys/types.h>
#include <regex.h>

enum {
	NOTYPE = 256,
	EQ,
	HEXNUM,
	NUM,
	MARK,
	REGNAME,
	NOTEQ,
	AND,
	OR,
	NEG,
	DEREF

	/* TODO: Add more token types */

};

static struct rule {
	char *regex;
	int token_type;
} rules[] = {

	/* TODO: Add more rules.
	 * Pay attention to the precedence level of different rules.
	 */

	{" +",	NOTYPE},										 // spaces
	{"\\+", '+'},													// plus
	{"==", EQ},													  // equal
	{"0x[0-9a-fA-F]+",HEXNUM},               //hexadecimal number
	{"[0-9]{1,10}",NUM},                 			   //decimal number
	{"\\b[a-zA-Z0-9_]+\\b",MARK},		   // 变量
	{"\\$[a-z0-9]{2,4}",REGNAME},                 //register name
	{"\\(",'('},                                                     //left parenthesis
	{"\\)",')'},             										 //right parenthesis
	{"\\*",'*'},            										//multiply
	{"\\/",'/'},             										//divide
	{"\\-",'-'},             										 //minus
	{"!=",NOTEQ},           								//not equal
	{"&&",AND},               								  //logical and
	{"\\|\\|",OR},             	 								//logical or
	{"!",'!'},                                                        //logical not
	{"\\%",'%'}                                                //mod
};

#define NR_REGEX (sizeof(rules) / sizeof(rules[0]) )

static regex_t re[NR_REGEX];

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
	int i;
	char error_msg[128];
	int ret;

	for(i = 0; i < NR_REGEX; i ++) {
		ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
		if(ret != 0) {
			regerror(ret, &re[i], error_msg, 128);
			Assert(ret == 0, "regex compilation failed: %s\n%s", error_msg, rules[i].regex);
		}
	}
}

typedef struct token {
	int type;
	char str[32];
} Token;

Token tokens[32];
int nr_token;

static bool make_token(char *e) {
	int position = 0;
	int i;
	regmatch_t pmatch;
	
	nr_token = 0;

	while(e[position] != '\0') {
		/* Try all rules one by one. */
		for(i = 0; i < NR_REGEX; i ++) {
			if(regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
				char *substr_start = e + position;
				int substr_len = pmatch.rm_eo;

				//Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s", i, rules[i].regex, position, substr_len, substr_len, substr_start);
				position += substr_len;

				/* TODO: Now a new token is recognized with rules[i]. Add codes
				 * to record the token in the array `tokens'. For certain types
				 * of tokens, some extra actions should be performed.
				 */

				switch(rules[i].token_type) {
					case NOTYPE:
						break;
					case HEXNUM:
					case NUM:
					case REGNAME:
					case MARK:
						
					default: 
						sprintf(tokens[nr_token].str,"%.*s",substr_len,substr_start);
						tokens[nr_token].type=rules[i].token_type;
						nr_token++;
				}

				break;
			}
		}

		if(i == NR_REGEX) {
			printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
			return false;
		}
	}

	return true; 
}

bool check_parentheses(int p,int q)
{
	int count=0;
	int i;
	if(tokens[p].type!='('||tokens[q].type!=')')
	{
		return false;
	}
	for(i=p;i<=q;i++)
	{
		if(count==0 && i!=p && i!=q)
		{
			return false;
		}
		if(tokens[i].type=='(')
		{
			count++;
		}
		else if(tokens[i].type==')')
		{
			count--;
		}
	}
	if(count==0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

static int op_level(int t)
{
	switch (t)
	{
	case '!': 
	case NEG: 
	case DEREF: 
		return 0;
	case '*': 
	case '/': 
	case '%': 
		return 1;
	case '+': 
	case '-': 
		return 2;
	case EQ: 
	case NOTEQ: 
		return 3;
	case AND: 
		return 4;
	case OR: 
		return 5;
	
	default:
		assert(0);
	}
}


static int op_cmp(int t1,int t2)
{
	return op_level(t1)-op_level(t2);
}

static int find_dominant(int p,int q,bool* success)
{
	int i;
	int count=0;
	int dominant_op=-1;
	for(i=p;i<=q;i++)
	{
		switch (tokens[i].type)
		{
		case  NUM: case HEXNUM: case MARK:case REGNAME: break;
		case '(':
			count++;
			break;

		case ')':
			count--;
			if(count<0)
			{
				*success = false;
				return 0;
			}
			break;
		
		default:
			if(count==0)
			{
				if(dominant_op==-1 || op_cmp(tokens[dominant_op].type,tokens[i].type)<0 || (op_cmp(tokens[dominant_op].type,tokens[i].type)==0 && tokens[i].type!='!' &&tokens[i].type!=NEG &&tokens[i].type!=DEREF ) )
					dominant_op = i;
			}
			break;
		}
	}
	*success = (dominant_op != -1);
	return dominant_op;
}

int eval(int p, int q, bool *success){
	if(*success == 0) return 0;
	if(p > q){
		*success = false;
		return 0;
	}
	else if(p == q){
		int n;
		if(tokens[p].type == NUM){
			sscanf(tokens[p].str,"%d",&n);
			*success = true;
			return n;
		}
		if(tokens[p].type == HEXNUM){
			sscanf(tokens[p].str,"%x",&n);
			*success = true;
			return n;
		}

		if(tokens[p].type == REGNAME){
			int i; *success = true;
			const char* reg_32[32] = {"$zero", "$at", "$v0", "$v1", "$a0", "$a1", "$a2", "$a3", 
																  "$t0", "$t1", "$t2", "$t3", "$t4", "$t5", "$t6", "$t7", 
																  "$s0", "$s1", "$s2", "$s3", "$s4", "$s5", "$s6", "$s7",
																  "$t8", "$t9","$k0", "$k1", "$gp", "$sp", "$fp", "$ra"};
			
			for(i = 0;i < 31;i++){
			   if(strcmp(tokens[p].str,reg_32[i]) == 0){ n = cpu.gpr[i]._32; break;}
			  
			}
			
			if(strcmp(tokens[p].str,"$pc") == 0)
			n = cpu.pc;
	
			return n;
		}
		else{
			*success = false;
			return 0;
		}
	}
	else if(check_parentheses(p,q) == true){
		return eval(p + 1,q - 1,success);
	}
	else{
		int op = find_dominant(p,q,success);
		int op_type = tokens[op].type;
		if(op_type == '!' || op_type == NEG || op_type == DEREF) {
			int val = eval(op + 1, q, success);
			if(!*success) { return 0; }

		switch(op_type){
				case '!': return !val;
				case NEG: return -val;
				case DEREF: return mem_read(val, 4);
			default: assert(0); return 0;
		}
		}
	
		int value1 = eval(p,op - 1,success);
		int value2 = eval(op + 1,q,success);
		
		switch(op_type){
			case '+' : return value1 + value2; break;
			case '-' : return value1 - value2; break;
			case '*': return value1*value2; break;
			case '/': return value1/value2; break;
			case AND : return value1 && value2; break;
			case OR: return value1 || value2; break;
			case NOTEQ: return value1 != value2; break;
			case EQ: return value1 == value2; break;
			default: assert(0); return 0;
		}
	   }
}


uint32_t expr(char *e, bool *success) {
	if(!make_token(e)) {
		*success = false;
		return 0;
	}

	/* TODO: Insert codes to evaluate the expression. */
	//panic("please implement me");

	*success = true;
	int i;
	for(i=0;i<nr_token;i++)
	{
		if( (tokens[i].type=='*' || tokens[i].type=='-' ) && (i==0 || tokens[i-1].type=='+' || tokens[i-1].type == '-' || tokens[i-1].type=='*' || tokens[i-1].type=='/' || tokens[i-1].type=='(' || tokens[i-1].type==EQ ||tokens[i-1].type==NOTEQ) )
			{
				if(tokens[i].type=='*')
					{ tokens[i].type=DEREF;}
				else if(tokens[i].type=='-')
					{ tokens[i].type=NEG;}
			}
	}

	uint32_t result=0;
	result=eval(0,nr_token-1,success);

	//panic("please implement me");
	return result;
}

